package leetcode.hot100;

/**
 * Created on 2021-01-22 。
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * 要求:
 * 1. 在原数组上进行操作，不能拷贝到额外的数组
 * 2. 尽量减少操作次数
 * https://leetcode-cn.com/problems/move-zeroes/
 * @author wll 1978992154@qq.com
 */
public class MoveZeroNode {
    public void moveZeroes(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0){
                // 删除当前0  并在数组的末尾添加0
                int zeroIndex = i;
            }
        }
    }

    /**
     * 使用双指针实现移动零
     * 实现思路： 如果快指针遇到了0 就后移一位 前指针不动  如果非零 那就一起后移 一次循环下来 快指针移动到了末位 而满指正到了最后一个
     * @param nums 数组
     */
    public void moveZerosByTwoPoint(int[] nums){

    }

    /**
     * 最笨的方式实现 遇到零就开始循环 找到第一个不为0的数据 交换内容 然后跳出 继续循环 这样的时间复杂度为 最坏O(n^2) 最好是O(n)
     * @param nums 处理过后的数组
     */
    public static void moveZerosBase(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0){
                for (int j = i; j < nums.length; j++) {
                    if (nums[j] != 0){
                        // 找到第一个不为0的元素 然后交换位置
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                        break;
                    }
                }
            }
        }
    }

    public static void displayArrays(int[] nums){
        for (int num : nums) {
            System.out.print(num+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int [] arr = new int[] {0,1,2,0,3,4,0,6,0};
        displayArrays(arr);
        moveZerosBase(arr);
        displayArrays(arr);
    }
}
